Telecommunications networks such as telephone and packet networks are made up of many switching nodes which are interconnected by links. A call is routed from an originating node to a destination node by way of intermediate nodes through one, two, and three or more links. Generally speaking, there are two routing schemes which exist separately or co-exist in the same network, sequential routing (hierarchical routing) and/or selective routing (occasionally called "dynamic", "high-performance", or "adaptive" routing). Despite the names, both are dynamic in the sense that routing paths are dynamically adjusted to the state of links and both exhibit high performance under certain traffic conditions. Regardless of routing, when node A initiates a request to connect to node B, node B, being the host of the destination link, must first accept the request.
In the sequential routing scheme, an ordered set of routes is scanned in the search for a free end-to-end path and the first encountered free path is allocated. The widely used hierarchical routing is a special case of sequential routing, and the so-called time-of-day routing is another form of sequential routing. The sequential routing scheme is easy to implement.
In selective routing, a predefined set of routes is examined in the search for a free path. When two or more free paths are available, the path selection is based on a comparison of the states of the free paths. In a well-utilized network serving steady traffic, selective routing is marginally better than sequential routing. However, the performance or efficiency difference widens as the traffic volatility increases. Short-term volatility may be caused by variation in demand, traffic composition, etc. Long-term volatility may be caused by multi-time-zone coverage. In the multi-service network, the selective routing far outperforms the sequential routing due to traffic variability which may increase by orders of magnitude due to:
different connection bit rate ("bandwidth") allocations; PA1 volatility of the traffic mixture; and PA1 asymmetry of bit rate ("bandwidth") requirements for the same connection (e.g., 10 Mb/s in one direction and 1 Kb/s in the opposite direction).
U.S. Pat. No. 4,679,189 (Olson et al, Jul. 7, 1987) is an example of selective routing. The patent describes an alternate routing arrangement for packet switched networks such as those of X.25 packet standards. According to the patent, the alternate routing control information includes a destination node index code identifying the destination node. The destination node index is used as address information by each node receiving a packet to read out the stored information at the node identifying the available paths and the algorithm to be used in selecting one of these paths for use in transmitting the packet towards the destination node. The identified algorithm is then executed to select the path to be used.
The selective routing scheme requires information on the state of the relevant links and can be implemented in either of two information control schemes, a distributed or centralized routing control scheme. These control schemes will be described in a more detailed manner later. In a network of ATM switches, a separate signaling network is unnecessary since both the traffic payload and the control messages can use the same medium. In addition, it may be argued that centralized control is undesirable in such a network.
The present invention is therefore concerned with improvement in performance of an ATM network which combines the benefits of sequential routing and selective routing. This routing scheme can be conveniently called hybrid routing. The ATM network of the present invention includes a distributed routing control based on negotiations between the originating and selected intermediate nodes only. This limited control can only affect the traffic which uses a direct link, or at most two links, between origin and destination. The part of the traffic which must use three or more links to destination must then follow a predetermined routing scheme. Two-link routes serve as a catalyst that balances the traffic.